package search;

/*
    二分查找的递归写法
 */
public class BinarySearchRecursion {

    public static void main(String[] args) {
        int[] array = new int[]{1, 3, 4, 5, 6, 8, 9, 15};
        int len = array.length;

        for (int i : array) {
            System.out.println(
                    binarySearchRecursion(array, i, 0, len)
            );
        }
    }

    public static int binarySearchRecursion(int[] array, int target, int left, int right) {
        if (left == right) {
            return left;
        }

        int leftIndex = left;
        int rightIndex = right;
        int mid = leftIndex + (rightIndex - rightIndex) / 2;

        if (array[mid] == target) {
            return mid;
        }

        if (array[mid] < target) {
            return binarySearchRecursion(array, target, mid + 1, right);
        }
        return binarySearchRecursion(array, target, left, mid - 1);
    }
}
